home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / filutil / bison110.zip / CLOSURE.C < prev    next >
C/C++ Source or Header  |  1990-06-26  |  8KB  |  383 lines
  1. /* Subroutines for bison
  2.    Copyright (C) 1984, 1989 Free Software Foundation, Inc.
  3.  
  4. This file is part of Bison, the GNU Compiler Compiler.
  5.  
  6. Bison is free software; you can redistribute it and/or modify
  7. it under the terms of the GNU General Public License as published by
  8. the Free Software Foundation; either version 1, or (at your option)
  9. any later version.
  10.  
  11. Bison is distributed in the hope that it will be useful,
  12. but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. GNU General Public License for more details.
  15.  
  16. You should have received a copy of the GNU General Public License
  17. along with Bison; see the file COPYING.  If not, write to
  18. the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  19.  
  20.  
  21. /* subroutines of file LR0.c.
  22.  
  23. Entry points:
  24.  
  25.   closure (items, n)
  26.  
  27. Given a vector of item numbers items, of length n,
  28. set up ruleset and itemset to indicate what rules could be run
  29. and which items could be accepted when those items are the active ones.
  30.  
  31. ruleset contains a bit for each rule.  closure sets the bits
  32. for all rules which could potentially describe the next input to be read.
  33.  
  34. itemset is a vector of item numbers; itemsetend points to just beyond the end
  35.  of the part of it that is significant.
  36. closure places there the indices of all items which represent units of
  37. input that could arrive next.
  38.  
  39.   initialize_closure (n)
  40.  
  41. Allocates the itemset and ruleset vectors,
  42. and precomputes useful data so that closure can be called.
  43. n is the number of elements to allocate for itemset.
  44.  
  45.   finalize_closure ()
  46.  
  47. Frees itemset, ruleset and internal data.
  48.  
  49. */
  50.  
  51. #include <stdio.h>
  52. #include "system.h"
  53. #include "machine.h"
  54. #include "new.h"
  55. #include "gram.h"
  56.  
  57.  
  58. extern short **derives;
  59.  
  60. void set_fderives();
  61. void set_firsts();
  62.  
  63. extern void RTC();
  64.  
  65. short *itemset;
  66. short *itemsetend;
  67. static unsigned *ruleset;
  68.  
  69. /* internal data.  See comments before set_fderives and set_firsts.  */
  70. static unsigned *fderives;
  71. static unsigned *firsts;
  72.  
  73. /* number of words required to hold a bit for each rule */
  74. static int rulesetsize;
  75.  
  76. /* number of words required to hold a bit for each variable */
  77. static int varsetsize;
  78.  
  79.  
  80. void
  81. initialize_closure(n)
  82. int n;
  83. {
  84.   itemset = NEW2(n, short);
  85.  
  86.   rulesetsize = WORDSIZE(nrules + 1);
  87.   ruleset = NEW2(rulesetsize, unsigned);
  88.  
  89.   set_fderives();
  90. }
  91.  
  92.  
  93.  
  94. /* set fderives to an nvars by nrules matrix of bits
  95.    indicating which rules can help derive the beginning of the data
  96.    for each nonterminal.  For example, if symbol 5 can be derived as
  97.    the sequence of symbols 8 3 20, and one of the rules for deriving
  98.    symbol 8 is rule 4, then the [5 - ntokens, 4] bit in fderives is set.  */
  99. void
  100. set_fderives()
  101. {
  102.   register unsigned *rrow;
  103.   register unsigned *vrow;
  104.   register int j;
  105.   register unsigned mask;
  106.   register unsigned cword;
  107.   register short *rp;
  108.  
  109.   int ruleno;
  110.   int i;
  111.  
  112.   fderives = NEW2(nvars * rulesetsize, unsigned) - ntokens * rulesetsize;
  113.  
  114.   set_firsts();
  115.  
  116.   rrow = fderives + ntokens * rulesetsize;
  117.  
  118.   for (i = ntokens; i < nsyms; i++)
  119.     {
  120.       vrow = firsts + ((i - ntokens) * varsetsize);
  121.       cword = *vrow++;
  122.       mask = 1;
  123.       for (j = ntokens; j < nsyms; j++)
  124.     {
  125.       if (cword & mask)
  126.         {
  127.           rp = derives[j];
  128.           while ((ruleno = *rp++) > 0)
  129.         {
  130.           SETBIT(rrow, ruleno);
  131.         }
  132.         }
  133.  
  134.       mask <<= 1;
  135.       if (mask == 0 && j + 1 < nsyms)
  136.         {
  137.           cword = *vrow++;
  138.           mask = 1;
  139.         }
  140.     }
  141.  
  142.       vrow += varsetsize;
  143.       rrow += rulesetsize;
  144.     }
  145.  
  146. #ifdef    DEBUG
  147.   print_fderives();
  148. #endif
  149.  
  150.   FREE(firsts);
  151. }
  152.  
  153.  
  154.  
  155. /* set firsts to be an nvars by nvars bit matrix indicating which items
  156.    can represent the beginning of the input corresponding to which other items.
  157.    For example, if some rule expands symbol 5 into the sequence of symbols 8 3 20,
  158.    the symbol 8 can be the beginning of the data for symbol 5,
  159.    so the bit [8 - ntokens, 5 - ntokens] in firsts is set. */
  160. void
  161. set_firsts()
  162. {
  163.   register unsigned *row;
  164. /*   register int done; JF unused */
  165.   register int symbol;
  166.   register short *sp;
  167.   register int rowsize;
  168.  
  169.   int i;
  170.  
  171.   varsetsize = rowsize = WORDSIZE(nvars);
  172.  
  173.   firsts = NEW2(nvars * rowsize, unsigned);
  174.  
  175.   row = firsts;
  176.   for (i = ntokens; i < nsyms; i++)
  177.     {
  178.       sp = derives[i];
  179.       while (*sp >= 0)
  180.     {
  181.       symbol = ritem[rrhs[*sp++]];
  182.       if (ISVAR(symbol))
  183.         {
  184.           symbol -= ntokens;
  185.           SETBIT(row, symbol);
  186.         }
  187.     }
  188.  
  189.       row += rowsize;
  190.     }
  191.  
  192.   RTC(firsts, nvars);
  193.  
  194. #ifdef    DEBUG
  195.   print_firsts();
  196. #endif
  197. }
  198.  
  199.  
  200. void
  201. closure(core, n)
  202. short *core;
  203. int n;
  204. {
  205.   register int ruleno;
  206.   register unsigned word;
  207.   register unsigned mask;
  208.   register short *csp;
  209.   register unsigned *dsp;
  210.   register unsigned *rsp;
  211.  
  212.   short *csend;
  213.   unsigned *rsend;
  214.   int symbol;
  215.   int itemno;
  216.  
  217.   rsp = ruleset;
  218.   rsend = ruleset + rulesetsize;
  219.   csend = core + n;
  220.  
  221.   if (n == 0)
  222.     {
  223.       dsp = fderives + start_symbol * rulesetsize;
  224.       while (rsp < rsend)
  225.     *rsp++ = *dsp++;
  226.     }
  227.   else
  228.     {
  229.       while (rsp < rsend)
  230.     *rsp++ = 0;
  231.  
  232.       csp = core;
  233.       while (csp < csend)
  234.     {
  235.       symbol = ritem[*csp++];
  236.       if (ISVAR(symbol))
  237.         {
  238.           dsp = fderives + symbol * rulesetsize;
  239.           rsp = ruleset;
  240.           while (rsp < rsend)
  241.         *rsp++ |= *dsp++;
  242.         }
  243.     }
  244.     }
  245.  
  246.   ruleno = 0;
  247.   itemsetend = itemset;
  248.   csp = core;
  249.   rsp = ruleset;
  250.   while (rsp < rsend)
  251.     {
  252.       word = *rsp++;
  253.       if (word == 0)
  254.     {
  255.       ruleno += BITS_PER_WORD;
  256.     }
  257.       else
  258.     {
  259.       mask = 1;
  260.       while (mask)
  261.         {
  262.           if (word & mask)
  263.         {
  264.           itemno = rrhs[ruleno];
  265.           while (csp < csend && *csp < itemno)
  266.             *itemsetend++ = *csp++;
  267.           *itemsetend++ = itemno;
  268.         }
  269.  
  270.           mask <<= 1;
  271.           ruleno++;
  272.         }
  273.     }
  274.     }
  275.  
  276.   while (csp < csend)
  277.     *itemsetend++ = *csp++;
  278.  
  279. #ifdef    DEBUG
  280.   print_closure(n);
  281. #endif
  282. }
  283.  
  284.  
  285. void
  286. finalize_closure()
  287. {
  288.   FREE(itemset);
  289.   FREE(ruleset);
  290.   FREE(fderives + ntokens * rulesetsize);
  291. }
  292.  
  293.  
  294.  
  295. #ifdef    DEBUG
  296.  
  297. print_closure(n)
  298. int n;
  299. {
  300.   register short *isp;
  301.  
  302.   printf("\n\nn = %d\n\n", n);
  303.   for (isp = itemset; isp < itemsetend; isp++)
  304.     printf("   %d\n", *isp);
  305. }
  306.  
  307.  
  308.  
  309. print_firsts()
  310. {
  311.   register int i;
  312.   register int j;
  313.   register unsigned *rowp;
  314.   register unsigned cword;
  315.   register unsigned mask;
  316.  
  317.   extern char **tags;
  318.  
  319.   printf("\n\n\nFIRSTS\n\n");
  320.  
  321.   for (i = ntokens; i < nsyms; i++)
  322.     {
  323.       printf("\n\n%s firsts\n\n", tags[i]);
  324.  
  325.       rowp = firsts + ((i - ntokens) * vrowsize);
  326.  
  327.       cword = *rowp++;
  328.       mask = 1;
  329.       for (j = 0; j < nsyms; j++)
  330.     {
  331.       if (cword & mask)
  332.         printf("   %s\n", tags[j + ntokens]);
  333.  
  334.       mask <<= 1;
  335.  
  336.       if (mask == 0 && j + 1 < nsyms)
  337.         {
  338.           cword = *rowp++;
  339.           mask = 1;
  340.         }
  341.     }
  342.     }
  343. }
  344.  
  345.  
  346.  
  347. print_fderives()
  348. {
  349.   register int i;
  350.   register int j;
  351.   register unsigned *rp;
  352.   register unsigned cword;
  353.   register unsigned mask;
  354.  
  355.   extern char **tags;
  356.  
  357.   printf("\n\n\nFDERIVES\n");
  358.  
  359.   for (i = ntokens; i < nsyms; i++)
  360.     {
  361.       printf("\n\n%s derives\n\n", tags[i]);
  362.       rp = fderives + i * rrowsize;
  363.       cword = *rp++;
  364.       mask = 1;
  365.       for (j = 0; j <= nrules; j++)
  366.         {
  367.       if (cword & mask)
  368.         printf("   %d\n", j);
  369.  
  370.       mask <<= 1;
  371.       if (mask == 0 && j + 1 < nrules)
  372.         {
  373.           cword = *rp++;
  374.           mask = 1;
  375.         }
  376.     }
  377.     }
  378.  
  379.   fflush(stdout);
  380. }
  381.  
  382. #endif
  383.